/*
题目: 吃掉 N 个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

    吃掉一个橘子。
    如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
    如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges
 */
public class MinDays {
    // 表示剩下几个 橘子 的时候, 最少的天数
    Map<Integer, Integer> map = new HashMap<> ();

    public int minDays(int n) {
        if (n <= 1) return n;
        if (map.containsKey(n)) return map.get(n);

        // 吃 一半 个橘子之前, 最多 多吃 一个橘子, 保证可以吃一半
        int res1 = minDays(n >> 1) + 1 + n % 2;
        // 吃 一半 个橘子之前, 最多 多吃 两个橘子, 保证可以吃剩 1/3
        int res2 = minDays(n / 3) + 1 + n % 3;
        int minn = Math.min(res1, res2);

        map.put(n, minn);
        return minn;
    }
}
